import java.util.ArrayList;

public class RadixSort {
    public static String[] sort(String[] arr, int length){
        ArrayList<String>[] buckets = new ArrayList[128];
        for (int i = 0; i < buckets.length; i++){
            buckets[i] = new ArrayList<>();
        }
        for (int i = length - 1; i >= 0; i--){
            for (String s : arr){
                buckets[s.charAt(i)].add(s);
            }
            int k = 0;
            for (ArrayList<String> bucket : buckets){
                for (String s : bucket){
                    arr[k++] = s;
                }
                bucket.clear();
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        String[] phoneNumbers = new String[10];
        phoneNumbers[0] = "13812345678";
        phoneNumbers[1] = "13912345678";
        phoneNumbers[2] = "13612345678";
        phoneNumbers[3] = "13712345678";
        phoneNumbers[4] = "13512345678";
        phoneNumbers[5] = "13412345678";
        phoneNumbers[6] = "15012345678";
        phoneNumbers[7] = "15112345678";
        phoneNumbers[8] = "15212345678";
        phoneNumbers[9] = "15712345678";

//        String[] phoneNumbers = new String[10];
//        phoneNumbers[0] = "138";
//        phoneNumbers[1] = "139";
//        phoneNumbers[2] = "136";
//        phoneNumbers[3] = "137";
//        phoneNumbers[4] = "135";
//        phoneNumbers[5] = "134";
//        phoneNumbers[6] = "150";
//        phoneNumbers[7] = "151";
//        phoneNumbers[8] = "152";
//        phoneNumbers[9] = "157";
        RadixSort.sort(phoneNumbers, 3);
        for (String phoneNumber : phoneNumbers) {
            System.out.println(phoneNumber);
        }
    }
}
